// bzoj1445
// 题意：给定n个(A, B)数对和limit，将其按顺序划分成若干部分，使得满足二个条件：
// 		 1.前面部分的任意一个的B都要大于后面部分的任意一个的A;
// 		 2.所有部分A的最大值的和<=limit;
// 		 要求所有部分B的和的最大值的最小值。
// 题解：good pro.对于问题，有单调性可以二分答案做，第一个限制可以预处理出来，把所有
//       划分点先处理出来，然后第二问就是dp。
//       普通的dp就是 f[i] = max(f[j] + max(a[j+1]..a[i])) (满足和小于等于Bmid),
//       这个dp是O(n^2)的，对于和的限制可以用单调队列。然后单调队列里面
//       按照A降序维护。并且可以看出来f是单调增的。
//       对于单调队列中第p位的状态，如果从这里转移很明显就是f[q[p-1]]+a[q[p]]，
//       （对于队首要特殊处理，维护一个left，表示当前单调队列维护的最左元素
//       位置），然后每次转移都从单调队列中取个最小值，这个可以用priority_queue
//       或者平衡树搞定，如果用优先队列删除的时候只需要再用个删除数组标记就行。
//
//统计：220ms，too long, 1re, 4wa
//
// run: $exec < bfdiff.in
// opt: 0
// flag: -g
#include <cstdio>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>

struct data { long long a; long long b; };
struct que_data { long long a; long long p; };
struct state { long long key; long long p; long long from; };

bool operator<(state const & a, state const & b)
{
	return a.key > b.key;
}

long long const inf = (long long)(1) << 50;
long long const maxn = 50100;
data da[maxn];
data cuted[maxn];
long long max_to_right[maxn];
long long f[maxn];
long long limit, n, tot;

long long prefix_sum[maxn];

void get_cut()
{
	max_to_right[n + 1] = 0;
	for (long long i = n; i; i--)
		max_to_right[i] = std::max(max_to_right[i + 1], da[i].a);

	long long tb = inf; data cur; cur.a = cur.b = 0;
	for (long long i = 1; i <= n; i++) {
		tb = std::min(tb, da[i].b);
		cur.a = std::max(cur.a, da[i].a);
		cur.b += da[i].b;
		if (tb > max_to_right[i + 1]) {
			cuted[++tot] = cur;
			cur.a = cur.b = 0;
			tb = inf;
		}
	}
	prefix_sum[0] = 0;
	for (long long i = 1; i <= tot; i++) prefix_sum[i] = prefix_sum[i - 1] + cuted[i].b;
}

long long queue[4 * maxn];

bool judge(long long m)
{
	std::priority_queue<state> pq;
	std::vector<bool> del(tot + 1);
	long long left = 0, head = 1, tail = 0;
	for (long long i = 1; i <= tot; i++) {
		f[i] = inf;
		for (; prefix_sum[i] - prefix_sum[left] > m; ) left++;
		for (; head <= tail && queue[head] <= left; ) del[queue[head++]] = true;
		for (; head <= tail && cuted[i].a >= cuted[queue[tail]].a; ) del[queue[tail--]] = true;
		queue[++tail] = i;
		if (head <= tail){
			state tmp;
			tmp.key = f[queue[tail - 1]] + cuted[i].a;
			tmp.from = queue[tail - 1];
			tmp.p = i;
			pq.push(tmp);
		}
		for (; !pq.empty() && (pq.top().from <= left || del[pq.top().from] || del[pq.top().p]); )
			pq.pop();
		long long top = inf;
		if (!pq.empty()) top = pq.top().key;
		f[i] = std::min(f[left] + cuted[queue[head]].a, top);
	}
	return f[tot] <= limit;
}

int main()
{
	std::scanf("%lld %lld", &n, &limit);
	long long sum = 0;
	for (long long i = 1; i <= n; i++) {
		std::scanf("%lld %lld", &da[i].a, &da[i].b);
		sum += da[i].b;
	}
	get_cut();

	/*
	for (long long i = 1; i <= tot; i++) std::printf("%lld %lld\n", cuted[i].a, cuted[i].b);
	std::printf("%d\n", judge(42));
	return 0;
	*/

	long long l = 0, r = sum;
	while (l + 1 < r) {
		long long mid = (l + r) / 2;
		//std::printf("%lld\n", mid);
		if (judge(mid)) r = mid;
		else			l = mid;
	}
	if (judge(l)) r = l;
	std::printf("%lld\n", r);
}

